<!-- The documentation for the automaton input step view. -->

<HTML><HEAD>
<TITLE>Build LL(1) Parse Table</TITLE>
</HEAD><BODY>

<H1>Build LL(1) Parse Table</H1>

<CENTER><IMG SRC="images/LLtable.png" ALT="" WIDTH="414" HEIGHT="220" BORDER="1"><BR>LL(1) parse table building.</CENTER>

<P>The user may build a LL(1) parse table for a grammar with this operator.  A full discussion of the method of building an LL(1) parse table is far too elaborate for this documentation.  Rather, this assumes that one has some understanding of building LL(1) parse tables, and merely explains JFLAPs interface convention for helping the user complete this procedure.</P>

<P>The LL(1) parse table construction and parse tree construction algorithm is as described in the ``Dragon'' compiler book.  Put very loosely, the idea behind LL(1) parsing is that the grammar starts with the start symbol, and repeatedly attempts to replace variables with their right hand side expansion based on what the next symbol of the input is, until the input string is derived.</P>

<H2>Steps</H2>

<P>When the user first chooses the menu item to build the parse table, JFLAP first checks to make sure that the grammar is LL(1).  If it is not, then the user is warned and is given the option to abort.  Assuming the grammar is LL(1), or if the user wishes to continue in spite of the grammar not being LL(1), these following steps are completed in order:</P>

<OL>
<LI>The user first enters the <DFN>first sets</DFN> for each variable, i.e., the set of terminals that a variable can start with.  <VAR>!</VAR> serves as the special symbol for lambda.  This set is entered by the user as a simple string of symbols, without any delimiters: e.g., if the user wishes to indicate that <VAR>a</VAR>, <VAR>b</VAR>, and <VAR><IMG SRC="entities/lambda.png" WIDTH="9" HEIGHT="12" ALIGN="middle"></VAR> are in the first set, then the user enters <VAR>ab!</VAR> as a single non-spaced string.  When the user is finished defining the first sets, he or she may press "Next," and JFLAP will either move to defining the follow sets, or will notify the user about errors.</LI>

<LI>The user then enters the <DFN>follow sets</DFN> for each variable, i.e., the set of terminals that can immediately follow a variable in a derivation.  The input convention is the same as for the first sets, except that the <VAR>$</VAR> symbol indicates the end-of-string character.  When the user has finished, again "Next" may be pressed to move on or be notified of errors.</LI>

<LI>With the first and follow sets as a reference, it is possible to fill out the entries in the parse table.  Given a production <VAR>A <IMG SRC="entities/rarr.png" WIDTH="16" HEIGHT="7" ALIGN="middle"> <IMG SRC="entities/alpha.png" WIDTH="9" HEIGHT="9" ALIGN="middle"></VAR> and every symbol <VAR>b</VAR> in <VAR>FIRST(<IMG SRC="entities/alpha.png" WIDTH="9" HEIGHT="9" ALIGN="middle">)</VAR>, the <VAR>(b, A)</VAR> entry in the table gets <VAR><IMG SRC="entities/alpha.png" WIDTH="9" HEIGHT="9" ALIGN="middle"></VAR>.  Multiple entries in a table cell (possible only if the grammar is not LL(1)) are separated by spaces.  The <VAR>!</VAR> string represents a lambda production.
</OL>

<H2>Help</H2>

<P>Users may elect to let JFLAP do some or all of the work rather than entering data themselves.</P>

<DL>
<DT>Do Selected</DT>
<DD>In any of the above steps, the user enters input into cells in a table.  If the user selects any of these cells and elects to "Do Selected", the answer appropriate to the cells will be entered into those cells which are currently selected.  Non-selected cells shall be left alone.</DD>

<DT>Do Step</DT>
<DD>This will either complete all first sets, or all follow sets, or complete the parse table according to which step we are on.</DD>

<DT>Do All</DT>
<DD>This will do everything.  After pressing this, JFLAP should display a working parse table.
</DL>


<H2>Parsing Details</H2>

<P>The top figure shows a completed LL(1) parse table.  Once the table is completed, the user has the option to proceed to parsing strings using the table by pressing the "Parse" button.  The interface for that parsing is explained <A HREF="gui.grammar.parse.LLParsePane.html">here</A>.  If the original grammar was not LL(1) the user will not be able to use the parse table to parse strings.</P>

<!-- <P>Once a parse table is constructed, the user may parse as many strings as he or she wishes.  When parsing, the user enters a string, and then may step through the process of building a parse tree with that string.  During the course of parsing, the entry in the parse table used at that step is highlighted.  The progress of the parse is displayed graphically: the user may view either a non-inverted parse tree, an inverted parse tree, or a string derivation table.  If ever the parser detects an error (i.e., if the string was not accepted), the user is informed and the parser refuses to proceed.  A sample LL(1) parsing is shown in Figure~\ref{fig:llparse}.</P> -->

</BODY></HTML>
